package com.leo.datastruct.tree;

/**
 *
 * @author xuexiaolei
 * @version 2018年02月05日
 */
public class RBTree<T extends Comparable<T>> {
    private RBTNode<T> mRoot;

    private static final boolean RED = false;
    private static final boolean BLACK = true;

    class RBTNode<T extends Comparable<T>>{
        T key;
        RBTNode<T> left,right,parent;
        boolean color = RED;

        public RBTNode() {}
        public RBTNode(T key) {
            this.key = key;
        }
        public RBTNode(T key, RBTNode<T> left, RBTNode<T> right, RBTNode<T> parent, boolean color) {
            this.key = key;
            this.left = left;
            this.right = right;
            this.parent = parent;
            this.color = color;
        }
    }

    //########################### 常用小操作 start ##################################
    private RBTNode<T> parentOf(RBTNode<T> node) {
        return node!=null ? node.parent : null;
    }
    private boolean colorOf(RBTNode<T> node) {
        return node!=null ? node.color : BLACK;
    }
    private boolean isRed(RBTNode<T> node) {
        return ((node!=null)&&(node.color==RED)) ? true : false;
    }
    private boolean isBlack(RBTNode<T> node) {
        return !isRed(node);
    }
    private void setBlack(RBTNode<T> node) {
        if (node!=null) {node.color = BLACK;}
    }
    private void setRed(RBTNode<T> node) {
        if (node!=null) {node.color = RED;}
    }
    private void setParent(RBTNode<T> node, RBTNode<T> parent) {
        if (node!=null) {node.parent = parent;}
    }
    private void setColor(RBTNode<T> node, boolean color) {
        if (node!=null) {node.color = color;}
    }
    private RBTNode<T> leftOf(RBTNode<T> p) {
        return (p == null) ? null: p.left;
    }

    private RBTNode<T> rightOf(RBTNode<T> p) {
        return (p == null) ? null: p.right;
    }
    /**
    * (递归实现)查找"红黑树x"中键值为key的节点
    */
    private RBTNode<T> search(RBTNode<T> x, T key) {
        if (x==null) {return x;}

        int cmp = key.compareTo(x.key);
        if (cmp < 0) {
            return search(x.left, key);
        }else if (cmp > 0) {
            return search(x.right, key);
        }else {
            return x;
        }
    }
    public RBTNode<T> search(T key) {
        return search(mRoot, key);
    }
    //########################### 常用小操作 end ##################################
    //########################### 旋转 start ##################################
    /**
     * 对红黑树的节点(x)进行左旋转
     *
     * 左旋示意图(对节点x进行左旋)：
     *      px                              px
     *     /                               /
     *    x                               y
     *   /  \      --(左旋)-.           / \                #
     *  lx   y                          x  ry
     *     /   \                       /  \
     *    ly   ry                     lx  ly
     *
     *
     */
    private void leftRotate(RBTNode<T> x){
        // 设置x的右孩子为y
        RBTNode<T> y = x.right;

        //y的左节点转移给x，并且修正他的父节点
        x.right = y.left;
        if (y.left != null){ y.left.parent = x; }

        // 将 “x的父亲” 设为 “y的父亲”，同时修正父亲节点的左右孩子节点
        y.parent = x.parent;
        if (x.parent == null){
            this.mRoot = y;
        }else {
            if (x.parent.left == x){
                x.parent.left = y;
            }else {
                x.parent.right = y;
            }
        }

        // 将 “x” 设为 “y的左孩子”
        y.left = x;
        // 将 “x的父节点” 设为 “y”
        x.parent = y;
    }

    /**
     * 对红黑树的节点(y)进行右旋转
     *
     * 右旋示意图(对节点y进行左旋)：
     *            py                               py
     *           /                                /
     *          x                                y
     *         /  \      --(右旋)-.            /  \                     #
     *        y   rx                           ly   x
     *       / \                                   / \                   #
     *      ly  ry                                ry  rx
     *
     */
    private void rightRotate(RBTNode<T> x){
        // 设置x的左孩子为y
        RBTNode<T> y = x.left;

        //y的右节点转移给x，并且修正这个节点的父节点
        x.left = y.right;
        if (y.right != null){ y.right.parent = x; }

        // 将 “x的父亲” 设为 “y的父亲”，同时修正父亲节点的左右孩子节点
        y.parent = x.parent;
        if (x.parent == null){
            this.mRoot = y;
        }else {
            if (x.parent.left == x){
                x.parent.left = y;
            }else {
                x.parent.right = y;
            }
        }

        // 将 “x” 设为 “y的右孩子”
        y.right = x;
        // 将 “x的父节点” 设为 “y”
        x.parent = y;
    }
    //########################### 旋转 end ##################################

    //########################### 插入 start ##################################
    public void insert(T key){
        RBTNode<T> node = new RBTNode<>(key);
        insert(node);
    }
    private void insert(RBTNode<T> node){
        RBTNode<T> x = this.mRoot;
        RBTNode<T> y = null;        //查找到的父节点
        int cmp;
        //找到要插入的节点
        while (x != null){
            y = x;
            cmp = node.key.compareTo(x.key);
            if (cmp < 0){
                x = x.left;
            }else if (cmp > 0){
                x = x.right;
            }else {
                throw new RuntimeException("不能插入相同节点");
            }
        }
        //更正节点的父节点和子节点引用
        node.parent = y;
        if (y == null){
            this.mRoot = node;
        }else {
            cmp = node.key.compareTo(y.key);
            if (cmp < 0){
                y.left = node;
            }else {
                y.right = node;
            }
        }

        insertFixUp(node);
    }

    /**
     * node节点插入后的调整方法
     * @param node
     */
    private void insertFixUp(RBTNode<T> node) {
        RBTNode<T> p;//父节点  parent简写
        RBTNode<T> g;//祖父节点  grandparent简写
        RBTNode<T> u;//叔父节点  uncle简写

        // 若“父节点存在，并且父节点的颜色是红色”
        while ( (p=node.parent)!=null && isRed(p)){
            g = parentOf(p);
            //若“父节点”是“祖父节点的左孩子”
            if (p == g.left){
                u = g.right;
                // Case 1条件：叔叔节点是红色。将父节点、叔父节点涂黑，祖父节点涂红，然后考虑祖父节点即可
                if (u!=null && isRed(u)){
                    setBlack(p);
                    setBlack(u);
                    setRed(g);
                    node = g;
                    continue;
                }
                // Case 2条件：叔叔是黑色，且当前节点是右孩子，将父节点左旋，转换成Case 3
                if (p.right == node){
                    RBTNode<T> temp;
                    leftRotate(p);
                    temp = p;
                    p = node;
                    node = temp;
                }
                // Case 3条件：叔叔是黑色，且当前节点是左孩子。替换祖父节点和父节点的颜色，然后祖父节点右旋即可
                setBlack(p);
                setRed(g);
                rightRotate(g);
            }else {
            //若“父节点”是“祖父节点的右孩子”,同上面类似，只是交换了位置而已
                u = g.left;
                if (u!=null && isRed(u)){
                    setBlack(u);
                    setBlack(p);
                    setRed(g);
                    node = g;
                    continue;
                }

                if (p.left == node){
                    RBTNode<T> temp;
                    rightRotate(p);
                    temp = p;
                    p = node;
                    node = temp;
                }

                setBlack(p);
                setRed(g);
                leftRotate(g);
            }
        }
        setBlack(this.mRoot);
    }

    //########################### 插入 end ##################################

    //########################### 删除 start ##################################
    public void remove(T key){
        RBTNode<T> node;
        if ((node = search(key)) != null){ remove(node); }
    }
    private void remove(RBTNode<T> node) {
        RBTNode<T> replace;
        // 被删除节点的"左右孩子都不为空"的情况，经过转换后成为最多只有一个孩子的情况
        if ( node.left!=null && node.right!=null ){
            //记录实际上被删的后继节点【前驱节点当然也可以】
            replace = node.right;
            while (replace.left != null){
                replace = replace.left;
            }
            //替换节点的值,然后考虑replace的单孩子情况即可
            node.key = replace.key;
            node = replace;
        }

        replace = (node.left == null)?node.right:node.left;
        //有一个孩子节点的情况
        if (replace != null){
            //处理替代节点的父节点
            replace.parent = node.parent;
            if (node.parent == null){
                mRoot = replace;
            }else if (node.parent.left == node){
                node.parent.left = replace;
            }else {
                node.parent.right = replace;
            }
            //方便回收
            node.left=node.right=node.parent=null;
            //如果被删节点是黑色的话，需要调整
            if (node.color == BLACK){
                deleteFixUp(replace);
            }
        }
        //没有孩子节点的情况
        else if (node.parent == null){
            //如果node是唯一节点
            mRoot = null;
        }else {
            if (node.color == BLACK){
                deleteFixUp(node);
            }
            if (node.parent != null) {
                if (node == node.parent.left) {
                    node.parent.left = null;
                }else if (node == node.parent.right){
                    node.parent.right = null;
                }
                node.parent = null;
            }
        }

    }

    private void deleteFixUp(RBTNode<T> n) {
        while (n!=mRoot && n.color==BLACK){
            if (n == leftOf(parentOf(n))){
                //n是父节点的左孩子
                RBTNode<T> s = rightOf(parentOf(n));//n节点的兄弟节点，sibling
                //如果兄弟节点是红色的，那就父节点左旋，并和兄弟节点换色，最后给了n一个黑色的兄弟节点：之后的s全是黑色考虑即可
                if (colorOf(s) == RED){
                    setColor(s, BLACK);
                    setColor(parentOf(n), RED);
                    leftRotate(parentOf(n));
                    s = rightOf(parentOf(n));
                }

                if (colorOf(leftOf(s))==BLACK && colorOf(rightOf(s))==BLACK){
                    //如果兄弟节点的两个儿子都是黑色的，那就把兄弟节点变红，考虑父节点即可
                    setColor(s, RED);
                    s = parentOf(s);
                }else {
                    //即左节点是红色的情况，那就将它旋转换色处理，变为 右节点是红色的情况
                    if (colorOf(rightOf(s)) == BLACK){
                        setColor(leftOf(s), BLACK);
                        setColor(s, RED);
                        rightRotate(s);
                        s = rightOf(parentOf(n));
                    }
                    //右节点是红色
                    setColor(s, colorOf(parentOf(n)));
                    setColor(parentOf(n), BLACK);
                    setColor(rightOf(s), BLACK);
                    leftRotate(parentOf(n));
                    n = mRoot;
                }
            } else{
                //n是父节点的右孩子，与上面类似！
                RBTNode<T> s = leftOf(parentOf(n));//n节点的兄弟节点，sibling
                //如果兄弟节点是红色的
                if (colorOf(s) == RED){
                    setColor(s, BLACK);
                    setColor(parentOf(n), RED);
                    rightRotate(parentOf(n));
                    s = leftOf(parentOf(n));
                }

                if (colorOf(leftOf(s))==BLACK && colorOf(rightOf(s))==BLACK){
                    //如果兄弟节点的两个儿子都是黑色的，那就把兄弟节点变红，考虑父节点即可
                    setColor(s, RED);
                    s = parentOf(s);
                }else {
                    //即右节点是红色的情况，那就将它旋转换色处理，变为 左节点是红色的情况
                    if (colorOf(leftOf(s)) == BLACK){
                        setColor(rightOf(s), BLACK);
                        setColor(s, RED);
                        leftRotate(s);
                        s = leftOf(parentOf(n));
                    }
                    //左节点是红色
                    setColor(s, colorOf(parentOf(n)));
                    setColor(parentOf(n), BLACK);
                    setColor(leftOf(s), BLACK);
                    rightRotate(parentOf(n));
                    n = mRoot;
                }
            }
        }
        setColor(n, BLACK);
    }
    //########################### 删除 end ##################################

}
